\section{Introducci\'on}
\subsection{Explicacion del algoritmo}
Para obtener la soluci\'on exacta, la manera que utilizaremos basicamente es probar todas las convinaciones de caminos posibles entre $u$ y $v$ y elegir aquella que tenga $W1 < K$ y $W2$ minimo.
\\
Para ello utilizaremos un backtraking, al que ademas aplicaremos algunas podas inteligentes cosa de hacelerar su velocidad de ejecuci\'on. La idea general del algoritmo, entonces, ser\'a, a la solucion parcial que hasta ahora gener\'e, chequeo que cumpla que $W1 < K$, en caso de no cumplir, podo esa rama, luego chequeo que $W2$ sea menor a la mejor solucion encontrada hasta el momento, sin\'o lo es, podo. Entonces, en este punto me fijo si el ultimo nodo que agreg\'e, es $v$, si lo es, me guardo la solucion y vuelvo a atras. Si no es $v$, chequeo si la soluci\'on generada hasta el momento tiene algun ciclo, en caso afirmativo, podo, ya que debe existir una soluci\'on sin ciclos mejor que tambien cumpla. Llegado este paso, agrego un nuevo nodo a la solucion parcial, y vuelvo a iterar.
\\
Escrito de una manera mas formal:
\\
\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{void Backtrack(Grafo, solucionParcial,mejorSolucion)}
  \STATE{Si W1 mayor que K}
   	\STATE{\quad return;} 
  \STATE{Si W2 mayor que mejorSolucion}
   	\STATE{\quad return;} 
  \STATE{Si el ultimo elemento de solucionParcial es $v$}
	\STATE{\quad guardo la solucion en mejorSolucion}
	\STATE{\quad return;}
  \STATE{Si solucionParcial tiene siclos}
	\STATE{\quad return;} 
  \STATE{\textbf{for i = 1; i < n; i++}}
    	\STATE{\quad si existe un eje entre el ultimo elemento de solucionParcial y el nodo $i$}
		\STATE{\quad \quad Agrego el nodo $i$ a la solucionParcial}
		\STATE{\quad \quad Backtrack(Grafo, solucionParcial,mejorSolucion)}
		\STATE{\quad \quad Quito el nodo $i$ de la solucionParcial}
\end{algorithmic}
\end{algorithm}
\\
\subsection{Cota de complegidad}
La cota recrusiva para el algoritmo, en el caso en el que en ningun momento pueda podarse, ser\'a $$T(x) = nT(x-1) + n$$ 
\\
Con el caso base:
\\
$$T(1)=n$$
\\
Luego es facil ver que esta funcion recursiva es $$T(x) = n^x +n^{x-1}$$
\\
Entonces la cota es de $O(n^n+n^{n-1})$
\\
\subsection{Experimentaci\'on}
\\
Para la experimentacion para este algoritmo utilizaremos un generador de entradas que crear\'a grafos completos, unos con $w1$ y $w2$ elegidos al azar, y otros con un $w1$ y $w2$ elegidos de manera "tendenciosa" para que el algoritmo no pueda realizar casi ninguna poda y se vea obligado a probar todos los casos posibles.
\\
Caso random:
\\
(grafico)
\\
Peores casos:
\\
(grafico)
\\
Como puede verse, el peor caso hace que la performance del algoritmo sea terrible. Estos casos surgen principalmente de la manera deterministica en que en que se eligen las aritas a ser evaluadas en cada paso. Una mejora que podr\'ia mejorar drasticamente el tiempo de ejecucion del algoritmo en estos casos, es que el siguiente vertice que se explora se elija de manera aleatoria. De esa manera, se eliminar\'ian estos posibles peores casos.
\\
